package edu.whu.rose.clock.ssql.util;

import java.util.ArrayList;
import java.util.Date;
import java.util.ListIterator;

public class Merger {
	
	//For testing methods.
	public static void main(String[] args) {
//		int[][] set = {{1,3,5},{1,3,5,7},{1,2,3,4},{2,3,6,7}};
//		int[] result = unionVertexSequences(set);
//		for (int i = 0; i < result.length; i++) {
//			System.out.print(result[i] + "  ");
//		}
		
		int[] x = {1,3,5,7,9};
		DoubleSequentialIntMap sim = new DoubleSequentialIntMap();
		sim.insertToColumn(1, 3);
		sim.insertToColumn(2, 3);
		sim.insertToColumn(6, 8);
		sim.insertToColumn(1, 1);
		sim.insertToColumn(1, 2);
		sim.insertToColumn(5, 3);
		sim.insertToColumn(3, 4);
		sim.insertToColumn(2, 5);
		sim.insertToColumn(3, 6);
		sim.insertToColumn(6, 7);
		sim.insertToColumn(7, 8);
		sim.insertToColumn(8, 9);
		DoubleSequentialIntMap result = Merger.rightUnion(sim, x);
		result.print();
	}

	//Assume that "sequence" is a totally sequentially organized array.
	public static int[] unionVertexSequences(int[][] sequence) {
		Date start = new Date();
		ArrayList<Integer> nums = new ArrayList<Integer>();
		
		if (sequence[0] != null) {
			for (int i = 0; i < sequence[0].length; i++) {
				boolean match = true;
				for (int j = 1; j < sequence.length; j++) {
					if (match) {
						match = false;
						
						int low = 0;
						int mid = 0;
						int top = sequence[j].length - 1;
						
						while (low <= top) {
							mid = (low + top) / 2;
							if (sequence[0][i] < sequence[j][mid]) {
								top = mid - 1;
							}
							else if (sequence[0][i] > sequence[j][mid]) {
								low = mid + 1;
							}
							else if (sequence[0][i] == sequence[j][mid]) {
								match = true;
								break;
							}
						}
					}
					else {
						break;
					}
				}
				if (match) {
					nums.add(new Integer(i));
				}
			}
			
			int[] result = new int[nums.size()];
			ListIterator<Integer> it = nums.listIterator();
			int i = 0;
			while (it.hasNext()) {
				result[i] = sequence[0][it.next().intValue()];
				i++;
			}
			Date end = new Date();
			System.out.println("Time exhausted for unioning vertex sequences: " + (end.getTime() - start.getTime()) + "ms");
			return result;
		}
		
		return null;
	}
	
	public static DoubleSequentialIntMap rightUnion(DoubleSequentialIntMap dsim, int[] array) {
		DoubleSequentialIntMap result = new DoubleSequentialIntMap();
		if (array.length > dsim.getColumnKeyCapacity()) {
			int low = 0;
			for (int i = 0; i < dsim.getColumnKeyCapacity(); i++) {
				int mid = 0;
				int top = array.length - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (dsim.getColumnKey(i) < array[mid]) {
						top = mid - 1;
					}
					else if (dsim.getColumnKey(i) > array[mid]) {
						low = mid + 1;
					}
					else if (dsim.getColumnKey(i) == array[mid]) {
						result.insertColumn(dsim.getColumnKey(i), dsim.getColumnValues(i), 
								dsim.getColumnValueSize(i), dsim.getColumnValueCapacity(i));
						low = mid + 1;
						break;
					}
				}
			}
		}
		else {
			int low = 0;
			for (int i = 0; i < array.length; i++) {
				int mid = 0;
				int top = dsim.getColumnKeyCapacity() - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (array[i] < dsim.getColumnKey(mid)) {
						top = mid - 1;
					}
					else if (array[i] > dsim.getColumnKey(mid)) {
						low = mid + 1;
					}
					else if (array[i] == dsim.getColumnKey(mid)) {
						result.insertColumn(dsim.getColumnKey(mid), dsim.getColumnValues(mid), 
								dsim.getColumnValueSize(mid), dsim.getColumnValueCapacity(mid));
						low = mid + 1;
						break;
					}
				}
			}
		}
		return result;
	}
	
	public static Path rightUnion(Path path, int[] array) {
		Path result = new Path();
		if (array.length > path.getColumnKeyCapacity()) {
			int low = 0;
			for (int i = 0; i < path.getColumnKeyCapacity(); i++) {
				int mid = 0;
				int top = array.length - 1;
				
				int column = path.getColumnKey(i);
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (column < array[mid]) {
						top = mid - 1;
					}
					else if (column > array[mid]) {
						low = mid + 1;
					}
					else if (column == array[mid]) {
						result.insertColumn(column, path.getColumnValues(i), 
								path.getColumnPaths(i), path.getColumnValueSize(i), 
								path.getColumnValueCapacity(i), path.getColumnPathSizes(i), 
								path.getColumnPathCapacities(i));
						
						low = mid + 1;
						break;
					}
				}
			}
		}
		else {
			int low = 0;
			for (int i = 0; i < array.length; i++) {
				int mid = 0;
				int top = path.getColumnKeyCapacity() - 1;
				
				int column = array[i];
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (array[i] < path.getColumnKey(mid)) {
						top = mid - 1;
					}
					else if (array[i] > path.getColumnKey(mid)) {
						low = mid + 1;
					}
					else if (array[i] == path.getColumnKey(mid)) {
						result.insertColumn(column, path.getColumnValues(i), 
								path.getColumnPaths(mid), path.getColumnValueSize(mid), 
								path.getColumnValueCapacity(mid), path.getColumnPathSizes(mid), 
								path.getColumnPathCapacities(mid));
						
						low = mid + 1;
						break;
					}
				}
			}
		}
		return result;
	}
	
	public static DoubleSequentialIntMap leftUnion(int[] array, DoubleSequentialIntMap dsim) {
		DoubleSequentialIntMap result = new DoubleSequentialIntMap();
		if (array.length > dsim.getRowKeyCapacity()) {
			int low = 0;
			for (int i = 0; i < dsim.getRowKeyCapacity(); i++) {
				int mid = 0;
				int top = array.length - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (dsim.getRowKey(i) < array[mid]) {
						top = mid - 1;
					}
					else if (dsim.getRowKey(i) > array[mid]) {
						low = mid + 1;
					}
					else if (dsim.getRowKey(i) == array[mid]) {
						result.insertRow(dsim.getRowKey(i), dsim.getRowValues(i), 
								dsim.getRowValueSize(i), dsim.getRowValueCapacity(i));
						low = mid + 1;
						break;
					}
				}
			}
		}
		else {
			int low = 0;
			for (int i = 0; i < array.length; i++) {
				int mid = 0;
				int top = dsim.getRowKeyCapacity() - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (array[i] < dsim.getRowKey(mid)) {
						top = mid - 1;
					}
					else if (array[i] > dsim.getRowKey(mid)) {
						low = mid + 1;
					}
					else if (array[i] == dsim.getRowKey(mid)) {
						result.insertRow(dsim.getRowKey(mid), dsim.getRowValues(mid), 
								dsim.getRowValueSize(mid), dsim.getRowValueCapacity(mid));
						low = mid + 1;
						break;
					}
				}
			}
		}
		return result;
	}
	
	
	
	public static Path midUnion(DoubleSequentialIntMap left, DoubleSequentialIntMap right) {
		Path result = new Path();
		if (left.getColumnKeyCapacity() > right.getRowKeyCapacity()) {
			int low = 0;
			for (int i = 0; i < right.getRowKeyCapacity(); i++) {
				int mid = 0;
				int top = left.getColumnKeyCapacity() - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (right.getRowKey(i) < left.getColumnKey(mid)) {
						top = mid - 1;
					}
					else if (right.getRowKey(i) > left.getColumnKey(mid)) {
						low = mid + 1;
					}
					else if (right.getRowKey(i) == left.getColumnKey(mid)) {
						for (int j = 0; j < left.getColumnValueCapacity(mid); j++) {
							for (int k = 0; k < right.getRowValueCapacity(i); k++) {
								result.doubleInsert(left.getColumnValues(mid)[j], 
										right.getRowValues(i)[k], "" + right.getRowKey(i));
							}
						}
						
						low = mid + 1;
						break;
					}
				}
			}
		}
		else {
			int low = 0;
			for (int i = 0; i < left.getColumnKeyCapacity(); i++) {
				int mid = 0;
				int top = right.getRowKeyCapacity() - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (left.getColumnKey(i) < right.getRowKey(mid)) {
						top = mid - 1;
					}
					else if (left.getColumnKey(i) > right.getRowKey(mid)) {
						low = mid + 1;
					}
					else if (left.getColumnKey(i) == right.getRowKey(mid)) {
						for (int j = 0; j < left.getColumnValueCapacity(i); j++) {
							for (int k = 0; k < right.getRowValueCapacity(mid); k++) {
								result.doubleInsert(left.getColumnValues(i)[j], 
										right.getRowValues(mid)[k], "" + left.getColumnKey(i));
							}
						}
						
						low = mid + 1;
						break;
					}
				}
			}
		}
		return result;
	}
	
	public static Path midUnion(Path left, DoubleSequentialIntMap right) {
		Path result = new Path();
		if (left.getColumnKeyCapacity() > right.getRowKeyCapacity()) {
			int low = 0;
			for (int i = 0; i < right.getRowKeyCapacity(); i++) {
				int mid = 0;
				int top = left.getColumnKeyCapacity() - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (right.getRowKey(i) < left.getColumnKey(mid)) {
						top = mid - 1;
					}
					else if (right.getRowKey(i) > left.getColumnKey(mid)) {
						low = mid + 1;
					}
					else if (right.getRowKey(i) == left.getColumnKey(mid)) {
						for (int j = 0; j < left.getColumnValueCapacity(mid); j++) {
							String[] vertex = left.getColumnPath(mid, j);
							for (int k = 0; k < right.getRowValueCapacity(i); k++) {
								for (int l = 0; l < vertex.length; l++) {
									result.doubleInsert(left.getColumnValues(mid)[j], 
											right.getRowValues(i)[k], vertex[l] + "-->" + right.getRowKey(i));
								}
							}
						}
						
						low = mid + 1;
						break;
					}
				}
			}
		}
		else {
			int low = 0;
			for (int i = 0; i < left.getColumnKeyCapacity(); i++) {
				int mid = 0;
				int top = right.getRowKeyCapacity() - 1;
				
				while (low <= top) {
					mid = (low + top) / 2;
					if (left.getColumnKey(i) < right.getRowKey(mid)) {
						top = mid - 1;
					}
					else if (left.getColumnKey(i) > right.getRowKey(mid)) {
						low = mid + 1;
					}
					else if (left.getColumnKey(i) == right.getRowKey(mid)) {
						for (int j = 0; j < left.getColumnValueCapacity(i); j++) {
							String[] vertex = left.getColumnPath(i, j);
							for (int k = 0; k < right.getRowValueCapacity(mid); k++) {
								for (int l = 0; l < vertex.length; l++) {
									result.doubleInsert(left.getColumnValues(i)[j], 
											right.getRowValues(mid)[k], vertex[l] + "-->" + left.getColumnKey(i));
								}
							}
						}
						
						low = mid + 1;
						break;
					}
				}
			}
		}
		return result;
	}

}
